﻿using System;
using System.Collections.Generic;

using System.Text;
using RoughJs.Helper;

namespace RoughJs.Ast
{
    /// <summary>
    /// 将对象映射为整数
    /// </summary>
    public class ObjToIntMap
    {

        public  class Iterator {

        public Iterator(ObjToIntMap master) {
            this.master = master;
        }

        public void init(Object[] keys, int[] values, int keyCount) {
            this.keys = keys;
            this.values = values;
            this.cursor = -1;
            this.remaining = keyCount;
        }

        public void start() {
            master.initIterator(this);
            next();
        }

        public bool done() {
            return remaining < 0;
        }

        public void next() {
            if (remaining == -1) Kit.codeBug();
            if (remaining == 0) {
                remaining = -1;
                cursor = -1;
            }else {
                for (++cursor; ; ++cursor) {
                    Object key = keys[cursor];
                    if (key != null && key != DELETED) {
                        --remaining;
                        break;
                    }
                }
            }
        }

        public Object getKey() {
            Object key = keys[cursor];
            if (key == UniqueTag.NULL_VALUE) { key = null; }
            return key;
        }

        public int getValue() {
            return values[cursor];
        }

        public void setValue(int value) {
            values[cursor] = value;
        }

        public ObjToIntMap master;
        private int cursor;
        private int remaining;
        private Object[] keys;
        private int[] values;
    }


        public ObjToIntMap()
            : this(4) { }
        public ObjToIntMap(int keyCountHint)
        {
            if (keyCountHint < 0) Kit.codeBug();
            // 当存诸的键表的增长 >= 3/4 最大的容量
            int minimalCapacity = keyCountHint * 4 / 3;
            int i;
            for (i = 2; (1 << i) < minimalCapacity; ++i) { }
            power = i;
            if (check && power < 2) Kit.codeBug();
        }

        public Object intern(object keyArg)
        {
            bool nullKey = false;
            if (keyArg == null)
            {
                nullKey = true;
                keyArg = UniqueTag.NULL_VALUE;
            }
            int index = ensureIndex(keyArg);
            values[index] = 0;
            return (nullKey) ? null : keys[index];
        }

        // Ensure key index creating one if necessary
        private int ensureIndex(Object key)
        {
            int hash = key.GetHashCode();
            int index = -1;
            int firstDeleted = -1;
            if (keys != null)
            {
                int fraction = hash * A;
                index = MathKit.foo(fraction, (32 - power));
                object test = keys[index];
                if (test != null)
                {
                    int N = 1 << power;
                    if (test == key || (values[N + index] == hash && test.Equals(key)))
                        return index;
                    if (test == DELETED)
                        firstDeleted = index;

                    //第一次搜索失败以后，再尝试
                    int mask = N - 1;
                    int step = tableLookupStep(fraction, mask, power);
                    int n = 0;
                    for (; ; )
                    {
                        if (check)
                        {
                            if (n >= occupiedCount) Kit.codeBug();
                            ++n;
                        }
                        index = (index + step) & mask;
                        test = keys[index];
                        if (test == null) { break; }
                        if (test == key || (values[N + index] == hash && test.Equals(key)))
                            return index;
                        if (test == DELETED && firstDeleted < 0)
                            firstDeleted = index;
                    }//end for 
                }

            }
            // Inserting of new key
            if (check && keys != null && keys[index] != null)
                Kit.codeBug();
            if (firstDeleted >= 0)
                index = firstDeleted;
            else
            {
                // Need to consume empty entry: check occupation level
                if (keys == null || occupiedCount * 4 >= (1 << power) * 3)
                {
                    // Too litle unused entries: rehash
                    rehashTable();
                    return insertNewKey(key, hash);
                }
                ++occupiedCount;
            }
            keys[index] = key;
            values[(1 << power) + index] = hash;
            ++keyCount;
            return index;
        }
        // Insert key that is not present to table without deleted entries
        // and enough free space
        private int insertNewKey(Object key, int hash)
        {
            if (check && occupiedCount != keyCount) Kit.codeBug();
            if (check && keyCount == 1 << power) Kit.codeBug();
            int fraction = hash * A;
            int index = MathKit.foo(fraction, (32 - power));
            int N = 1 << power;
            if (keys[index] != null)
            {
                int mask = N - 1;
                int step = tableLookupStep(fraction, mask, power);
                int firstIndex = index;
                do
                {
                    if (check && keys[index] == DELETED) Kit.codeBug();
                    index = (index + step) & mask;
                    if (check && firstIndex == index) Kit.codeBug();
                } while (keys[index] != null);
            }
            keys[index] = key;
            values[N + index] = hash;
            ++occupiedCount;
            ++keyCount;

            return index;
        }

        private void rehashTable()
        {
            if (keys == null)
            {
                if (check && keyCount != 0) Kit.codeBug();
                if (check && occupiedCount != 0) Kit.codeBug();
                int N = 1 << power;
                keys = new Object[N];
                values = new int[2 * N];
            }
            else
            {
                // Check if removing deleted entries would free enough space
                if (keyCount * 2 >= occupiedCount)
                {
                    // Need to grow: less then half of deleted entries
                    ++power;
                }
                int N = 1 << power;
                Object[] oldKeys = keys;
                int[] oldValues = values;
                int oldN = oldKeys.Length;
                keys = new Object[N];
                values = new int[2 * N];

                int remaining = keyCount;
                occupiedCount = keyCount = 0;
                for (int i = 0; remaining != 0; ++i)
                {
                    Object key = oldKeys[i];
                    if (key != null && key != DELETED)
                    {
                        int keyHash = oldValues[oldN + i];
                        int index = insertNewKey(key, keyHash);
                        values[index] = oldValues[i];
                        --remaining;
                    }
                }
            }
        }

        private static int tableLookupStep(int fraction, int mask, int power)
        {
            int shift = 32 - 2 * power;
            if (shift >= 0)
            {
                return (MathKit.foo(fraction, shift) & mask) | 1;
            }
            else
            {
                return (fraction & MathKit.foo(mask, -shift)) | 1;
            }
        }

        // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
        // See Knuth etc.
        private static int A = -1640531527;

        private static Object DELETED = new Object();

        // Structure of kyes and values arrays (N == 1 << power):
        // keys[0 <= i < N]: key value or null or DELETED mark
        // values[0 <= i < N]: value of key at keys[i]
        // values[N <= i < 2*N]: hash code of key at keys[i-N]


        /** Return array of present keys */
        public Object[] getKeys()
        {
            Object[] array = new Object[keyCount];
            getKeys(array, 0);
            return array;
        }

        public void getKeys(Object[] array, int offset)
        {
            int count = keyCount;
            for (int i = 0; count != 0; ++i)
            {
                Object key = keys[i];
                if (key != null && key != DELETED)
                {
                    if (key == UniqueTag.NULL_VALUE) { key = null; }
                    array[offset] = key;
                    ++offset;
                    --count;
                }
            }
        }

        //private static int tableLookupStep(int fraction, int mask, int power)
        //{
        //    int shift = 32 - 2 * power;
        //    if (shift >= 0)
        //    {
        //        return (MathKit.foo(fraction, shift) & mask) | 1;
        //    }
        //    else
        //    {
        //        return (fraction & MathKit.foo(mask, -shift)) | 1;
        //    }
        //}

        private int findIndex(Object key) {
        if (keys != null) {
            int hash = key.GetHashCode();
            int fraction = hash * A;
            int index = MathKit.foo(fraction , (32 - power));
            Object test = keys[index];
            if (test != null) {
                int N = 1 << power;
                if (test == key
                    || (values[N + index] == hash && test.Equals(key)))
                {
                    return index;
                }
                // Search in table after first failed attempt
                int mask = N - 1;
                int step = tableLookupStep(fraction, mask, power);
                int n = 0;
                for (;;) {
                    if (check) {
                        if (n >= occupiedCount) Kit.codeBug();
                        ++n;
                    }
                    index = (index + step) & mask;
                    test = keys[index];
                    if (test == null) {
                        break;
                    }
                    if (test == key
                        || (values[N + index] == hash && test.Equals(key)))
                    {
                        return index;
                    }
                }
            }
        }
        return -1;
    }


        public int size()
        {
            return keyCount;
        }
        public bool isEmpty()
        {
            return keyCount == 0;
        }

        public bool has(Object key)
        {
            if (key == null) { key = UniqueTag.NULL_VALUE; }
            return 0 <= findIndex(key);
        }

        /**
         * Get integer value assigned with key.
         * @return key integer value or defaultValue if key is absent
         */
        public int get(Object key, int defaultValue)
        {
            if (key == null) { key = UniqueTag.NULL_VALUE; }
            int index = findIndex(key);
            if (0 <= index)
            {
                return values[index];
            }
            return defaultValue;
        }

        /**
    * Get integer value assigned with key.
    * @return key integer value
    * @throws RuntimeException if key does not exist
    */
        public int getExisting(Object key)
        {
            if (key == null) { key = UniqueTag.NULL_VALUE; }
            int index = findIndex(key);
            if (0 <= index)
            {
                return values[index];
            }
            // Key must exist
            Kit.codeBug();
            return 0;
        }

        public void put(Object key, int value)
        {
            if (key == null) { key = UniqueTag.NULL_VALUE; }
            int index = ensureIndex(key);
            values[index] = value;
        }


        public Iterator newIterator()
        {
            return new Iterator(this);
        }
        public void initIterator(Iterator i)
        {
            i.init(keys, values, keyCount);
        }

        private Object[] keys;
        private int[] values;

        private int power;
        private int keyCount;
        private int occupiedCount; // == keyCount + deleted_count

        // If true, enables consitency checks
        private static bool check = false;
    }
}
